///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// * };
// */
//class Solution {
//public:
//    bool GetPath(stack<TreeNode*>& st, TreeNode* node, TreeNode* x)
//    {
//        if (node == nullptr) return false;
//
//        st.push(node);
//        if (node == x) return true;
//        if (GetPath(st, node->left, x) || GetPath(st, node->right, x))  return true;
//        st.pop();
//        return false;
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == nullptr) return nullptr;
//        stack<TreeNode*> stp, stq;
//        GetPath(stp, root, p);
//        GetPath(stq, root, q);
//
//        int num = stp.size() - stq.size();
//        num = abs(num);
//        if (stp.size() < stq.size())
//            while (num--) stq.pop();
//        else if (stp.size() > stq.size())
//            while (num--) stp.pop();
//
//        while (stp.top() != stq.top()) stp.pop(), stq.pop();
//
//        return stq.top();
//    }
//};
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// * };
// */
//class Solution {
//public:
//    bool IsInthetree(TreeNode* node, TreeNode* x)
//    {
//        if (node == nullptr) return false;
//
//        return node == x || IsInthetree(node->left, x) || IsInthetree(node->right, x);
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == nullptr) return nullptr;
//        if (root == p || root == q) return root;
//
//        bool pInLeft = IsInthetree(root->left, p);
//        bool pInRight = !pInLeft;
//        bool qInLeft = IsInthetree(root->left, q);
//        bool qInRight = !qInLeft;
//
//        if ((pInLeft && qInRight) || (pInRight && qInLeft)) return root;
//        else if ((pInLeft && qInLeft)) return lowestCommonAncestor(root->left, p, q);
//        else return lowestCommonAncestor(root->right, p, q);
//    }
//};